package src.leetcode.backtrack.medium_0017;

import java.lang.invoke.VarHandle;
import java.util.ArrayList;
import java.util.List;

public class letterCombinations {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.letterCombinations("23"));
    }
}

class Solution {
    List<String> ans = new ArrayList<>();
    StringBuffer sb = new StringBuffer();
    String digits;
    String[] phoneMap = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return ans;
        this.digits = digits;
        backtrack(0);
        return ans;
    }

    private void backtrack(int index) {
        if (index == digits.length()) {
            ans.add(sb.toString());
            return;
        }
        int digit = digits.charAt(index) - '0';
        String letters = phoneMap[digit];
        for(char letter: letters.toCharArray()){
            sb.append(letter);
            backtrack(index + 1);
            sb.deleteCharAt(sb.length() - 1); // 回溯
        }
    }
}
